<?php
/**
 * User: LRZ
 * Date: 2020/2/27
 * Time: 16:52
 */

$array     = [4.12, 6.421, 0.0023, 3.0, 2.138, 8.122, 4.12, 10.09];
$sortArray = bucketSort($array);
print_r($sortArray);

function bucketSort($array)
{
    /*
     *  桶排序实现思路：
     *    1. 得到数组的最大值和最小值
     *    2. 初始化桶
     *    3. 遍历原始数组，将元素放入相应桶中
     *    4. 对每个桶进行内部排序
     *    5. 输出所有桶内的元素
     */

    // 算出最大最小值
    $max = max($array);
    $min = min($array);

    // 初始化桶
    $bucketCount = (int)(count($array) / 2); // 桶数量
    $bucketSize  = (int)(($max - $min) / ($bucketCount - 1)); // 桶的区间跨度
    $buckets     = array();
    for ($i = 0; $i < $bucketCount; $i++) {
        $buckets[$i] = [];
    }

    // 遍历原始数组，将每个元素放入相应的桶中
    foreach ($array as $v) {
        $buckets[(int)(($v - $min) / $bucketSize)][] = $v;
    }

    // 对每个桶内部进行排序，然后遍历每个桶并输出结果
    $sortedArray = array();
    foreach ($buckets as $v) {
        sort($v); // 桶内部排序
        foreach ($v as $v2) {
            $sortedArray[] = $v2;
        }
    }
    return $sortedArray;
}